package 题目集.数学;

import org.junit.Test;

import java.util.Arrays;
import java.util.BitSet;

public class 质数 {

    @Test
    public void ch01(){
        System.out.println(isPrime(2));
        System.out.println(isPrime(49877));
    }
    /**
     * 判断一个数是否是质数.
     * 为什么可以sqrt(n)呢?
     * 因为如果n不是质数,那么n可以分解成两个数a*b,我们只需要n模上其中一个即可，设其中a<=b,那么a^2<=n,所以a<=sqrt(n)
     */
    public boolean isPrime(int n){
        if (n<2) return false;
        int m= (int) Math.sqrt(n);
        for (int i = 2; i <=m; i++) {
            if (n%i==0) return false;
        }
        return true;
    }

    @Test
    public void ch02(){
        divide(18);
        System.out.println("--------");
        divide(111);
        System.out.println("--------");
        divide(131);
        System.out.println("--------");
    }
    /**
     * 分解质因数。
     * 枚举所有的质数，如果是n的因数，那么就一直除下去。
     * 时间复杂度O(logn)到O(sqrt(n))
     */
    public void divide(int n) {
        //这里为什么可以是n/i？其实这里是从i到sqrt(n)。因为n中最多只有一个大于sqrt(n)的质因数。（如果有两个，那么它两乘一块就大于n了，与质因子定义矛盾）
        for (int i = 2; i <= n/i; i++) {
            if (n % i == 0) {   //这里可能会模上合数，但是不影响结果。因为在之前的循环中已经将合数的因数都除掉了。
                int s = 0;
                while (n % i == 0) {    //将所有i因数都除掉。
                    n /= i;
                    s++;
                }
                System.out.println(i + " " + s);
            }
        }
        //单独处理最后一个可能大于sqrt(n)的质因数。
        if (n>1){
            System.out.println(n+" "+1);
        }
    }

    @Test
    public void ch03Test(){
        int[] prime = getPrime1(132);
        for (int i : prime) {
            if (!isPrime(i)) System.out.println(i);
        }
        System.out.println(Arrays.toString(prime));
    }
    /**
     * 埃氏筛法：
     *  从2开始，将所有2的倍数都标记为合数，然后再从3开始，将所有3的倍数都标记为合数，以此类推将所有质数的倍数全标记未合数。
     *  时间复杂度O(nloglogn)约等于 n
     */
    public int[] getPrime1(int n){
        BitSet bitSet=new BitSet(n);
        bitSet.set(0);
        bitSet.set(1);
        int m= (int) Math.sqrt(n);
//        int m=n;
        for (int i = 2; i <= m; i++) {
            if (!bitSet.get(i)){
                for(int j = i+i; j <= n; j+=i) {
                    bitSet.set(j);
                }
            }
        }
        bitSet.flip(0,n+1);
        return bitSet.stream().toArray();
    }



    @Test
    public void ch04Test(){
        int[] prime = getPrime2(131);
        int[] prime1 = getPrime1(131);
        System.out.println(Arrays.equals(prime,prime1));
        System.out.println(prime1.length==prime.length);
        for (int i : prime) {
            if (!isPrime(i)) System.out.println(i);
        }
        System.out.println(Arrays.toString(prime));
    }
    /**
     * 线性筛法：
     *  在埃氏筛法中，我们是通过质数的倍数去排除合数的。
     *  但这可能会使得每个合数都被标记了多次，比如6被标记了2和3两次。
     *  线性筛法思想是通过每个合数的最小质因子去将该合数给排除掉。
     */
    public int[] getPrime2(int n){
        BitSet bitSet=new BitSet(n);
        bitSet.set(0);
        bitSet.set(1);
        int[] primes=new int[n];
        int cnt=0;
        for (int i = 2; i <n; i++) {
            if (!bitSet.get(i)){
                primes[cnt++]=i;
            }
            for (int j = 0; primes[j]*i < n; j++) { //因为 p[j]小于等于i的最小质因子。所以p[j]也是p[j]*i的最小质因子。
                bitSet.set(primes[j]*i);
                if (i%primes[j]==0) //当i是p[j]的倍数时，之后的i，可能是其他更小的质数的倍数。即无法保证 i*p[j]的最小质因子是p[j]。
                    break;
            }
        }
        return Arrays.copyOf(primes,cnt);
    }
}
